// 排序问题：
// 输入： n个数的一个序列 (a_1, a_2, ..., a_n)
// 输出：输出序列的一个排列 (a_1^', a_2^..., a_n^')
//       其中 a_1^' <= a_2^' <= ... <= a_n^'。

/// 将两个已排序的子切片合并为一个已排序的子切片（原地操作）。
///
/// 此函数接受一个可变切片 `arr` 和三个索引 p、q 和 r，满足
/// `p <= q < r` 的关系。它假定子切片 `arr[p..=q]` 和 `arr[q+1..=r]` 已经
/// 被排序，并将它们合并为一个单一的已排序子切片 `arr[p..=r]`。
///
/// 合并过程使用临时向量来存储子切片的副本，然后将它们按排序顺序
/// 合并回原切片。当元素相等时，来自左子切片的元素会被放置在右子切片
/// 元素之前，确保了稳定性。
///
/// # 参数
/// - `arr`: 实现 `Ord` trait 的元素的可变切片。
/// - p: 第一个已排序子切片的起始索引（包含）。
/// - q: 第一个已排序子切片的结束索引（包含）。
/// - r: 第二个已排序子切片的结束索引（包含）。
///
/// # 要求
/// - `p <= q < r`
/// - `arr[p..=q]` 和 `arr[q+1..=r]` 必须是 `arr` 内的有效索引
/// - `arr[p..=q]` 和 `arr[q+1..=r]` 中的元素必须已排序
///
/// # 异常
/// - 如果索引超出范围或不满足 `p <= q < r` 条件则会 panic
///
/// # 复杂度
/// - 时间复杂度: O(r - p + 1)
/// - 空间复杂度: O(r - p + 1) 用于临时存储
///
/// # 稳定性
/// - 这个合并操作是稳定的 - 在合并结果中，来自左子切片的相等元素
///   会出现在来自右子切片的相等元素之前。
fn merge<T: Ord + Clone>(arr: &mut [T], p: usize, q: usize, r: usize) {
    let n1 = q - p + 1;
    let n2 = r - q;

    let mut left = Vec::with_capacity(n1);
    let mut right = Vec::with_capacity(n2);

    for i in 0..n1 {
        left.push(arr[p + i].clone());
    }
    for j in 0..n2 {
        right.push(arr[q + 1 + j].clone());
    }

    let mut i = 0;
    let mut j = 0;
    for k in p..=r {
        if i < n1 && (j >= n2 || left[i] <= right[j]) {
            arr[k] = left[i].clone();
            i += 1;
        } else {
            arr[k] = right[j].clone();
            j += 1;
        }
    }
}

pub fn merge_sort<T: Ord + Clone>(arr: &mut [T], p: usize, r: usize) {
    if p < r {
        let q = (p + r) / 2;
        merge_sort(arr, p, q);
        merge_sort(arr, q + 1, r);
        merge(arr, p, q, r);
    }
}

mod tests {
    #[test]
    fn merge_sort() {
        use super::merge_sort;
        use crate::test_utils;
        let mut a = test_utils::gen_random_vec::<i32>(100);
        let r = a.len() - 1;
        merge_sort(a.as_mut_slice(), 0, r);
        test_utils::assert_vec_asc(&a);
    }
}
